/*
    KMP算法相关题目

    前置知识
    讲解084、讲解085 - 数位dp，本节课题目4需要
    讲解100 - KMP算法原理和代码详解

    KMP算法的内容分为两期
    上期为 KMP算法原理和代码详解
    本期为 KMP算法相关题目

    上节课提到
    求解s2的next数组时间复杂度O(n)，均摊下来，1个位置求next值的复杂度O(1)
    匹配的主流程时间复杂度O(n)，均摊下来，s1中1个位置的比对过程，跳转的代价O(1)

    很多和匹配相关的问题，都会使用next数组来加速匹配过程

    ================================================

    自动机又叫确定有限状态自动机，是对信号序列进行判定的数学模型
    比如，判定s1是否包含s2、判定s是否是回文，等等
    自动机并不是具体的算法、数据结构，只是数学模型，更多是概念上的内容
    每种自动机实现方式可能有多种

    常见的自动机
    前缀树，讲解044、讲解045
    KMP自动机，理解KMP算法即可，讲解100、讲解101
    回文自动机，理解Manacher算法即可，讲解103，下节课
    后缀自动机(SAM)，理解后缀数组的用法即可，【挺难】课程里会安排讲述
    AC自动机，本节课

    ================================================

    题目1
    最短循环节的长度
    给你一个字符串s，它一定是由某个循环节不断自我连接形成的
    题目保证至少重复2次，但是最后一个循环节不一定完整
    现在想知道s的最短循环节是多长
    测试链接 : https://www.luogu.com.cn/problem/P4391

    ================================================

    题目2
    不停删除之后剩下的字符串
    给定一个字符串s1，如果其中含有s2字符串，就删除最左出现的那个
    删除之后s1剩下的字符重新拼接在一起，再删除最左出现的那个
    如此周而复始，返回最终剩下的字符串
    测试链接 : https://www.luogu.com.cn/problem/P4824

    ================================================

    题目3
    二叉树中的链表
    给你一棵以root为根的二叉树、一个以head为头的链表
    在二叉树中，有很多一直向下的路径
    如果某个路径上的数值等于以head为头的整个链表
    返回True，否则返回False
    测试链接 : https://leetcode.cn/problems/linked-list-in-binary-tree/

    ================================================

    题目4
    找到所有好字符串
    给你两个长度为n的字符串s1和s2，以及一个字符串evil
    好字符串的定义为 : 长度为n，字典序大于等于s1，字典序小于等于s2，且不包含evil字符串
    返回好字符串的数量
    由于答案很大返回对1000000007取余的结果
    测试链接 : https://leetcode.cn/problems/find-all-good-strings/

*/